#include <stdbool.h>
#include "clib_container_hash_map.h"


#if CLIB_CPU_BIT64
#define MAX_POW_TWO (((size_t) 1) << 63)
#else
#define MAX_POW_TWO (((size_t) 1) << 31)
#endif

struct clib_container_hash_map_item {
    //键
    void *key;
    //值
    void *value;
    //hash值
    clib_uint64_t hash_value;
    //下一个节点
    struct clib_container_hash_map_item *next;
};

struct clib_container_hash_map {
    size_t capacity;
    size_t size;
    size_t threshold;
    clib_uint32_t hash_seed;
    int key_len;
    float load_factor;
    struct clib_container_hash_map_item **buckets;

    size_t (*hash_func)(const void *key, size_t length, clib_uint32_t seed);

    int (*key_cmp_func)(const void *k1, const void *k2, size_t key_length);

    void *(*mem_malloc_func)(size_t size);

    void (*mem_free_func)(void *block);

    void *(*mem_copy_func)(void *target,const void *src, size_t size);
};

int clib_container_hash_map_create_with_conf(struct clib_container_hash_map_conf *conf,
                                             struct clib_container_hash_map **map) {

    clib_check_if_true_return_value(conf == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(conf->hash_func == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(conf->key_compare_func == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(conf->mem_copy_func == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(conf->mem_malloc_func == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(conf->mem_free_func == NULL, CLIB_RES_PARAM_ERROR);

    if (conf->initial_capacity == 0){
        conf->initial_capacity = 8;
    }
    if (conf->load_factor == 0){
        conf->load_factor = 0.5f;
    }

    struct clib_container_hash_map *new_map = conf->mem_malloc_func(sizeof(struct clib_container_hash_map));
    if (new_map == NULL) {
        //分配失败
        return CLIB_RES_MEMORY_ERROR;
    }
    //分配bucket的内存空间
    new_map->capacity = clib_align_pow2(conf->initial_capacity);
    new_map->buckets = conf->mem_malloc_func(new_map->capacity * sizeof(struct clib_container_hash_map_item *));

    if (new_map->buckets == NULL) {
        //分配失败
        conf->mem_free_func(new_map);
        return CLIB_RES_MEMORY_ERROR;
    }

    new_map->hash_func = conf->hash_func;
    new_map->key_cmp_func = conf->key_compare_func;
    new_map->load_factor = conf->load_factor;
    new_map->hash_seed = conf->hash_seed;
    new_map->key_len = conf->key_length;
    new_map->size = 0;
    new_map->mem_malloc_func = conf->mem_malloc_func;
    new_map->mem_free_func = conf->mem_free_func;
    new_map->mem_copy_func = conf->mem_copy_func;
    new_map->threshold = new_map->capacity * new_map->load_factor;

    *map = new_map;
    return CLIB_RES_OK;
}


void clib_container_hash_map_destroy(struct clib_container_hash_map *map) {
    for (size_t i = 0; i < map->capacity; i++) {
        struct clib_container_hash_map_item *next = map->buckets[i];
        while (next) {
            struct clib_container_hash_map_item *tmp = next->next;
            map->mem_free_func(next);
            next = tmp;
        }
    }
    map->mem_free_func(map->buckets);
    map->mem_free_func(map);
}

static void
move_entries(struct clib_container_hash_map_item **src_bucket, struct clib_container_hash_map_item **dest_bucket,
             size_t src_size, size_t dest_size) {
    size_t i;
    for (i = 0; i < src_size; i++) {
        struct clib_container_hash_map_item *entry = src_bucket[i];

        while (entry) {
            struct clib_container_hash_map_item *next = entry->next;
            size_t index = entry->hash_value & (dest_size - 1);
            entry->next = dest_bucket[index];
            dest_bucket[index] = entry;
            entry = next;
        }
    }
}


static int resize(struct clib_container_hash_map *map, size_t new_capacity) {
    if (map->capacity == MAX_POW_TWO) {
        return CLIB_RES_MEMORY_ERROR;
    }
    struct clib_container_hash_map_item **new_buckets = map->mem_malloc_func(
            new_capacity * sizeof(struct clib_container_hash_map_item));
    if (!new_buckets) {
        return CLIB_RES_MEMORY_ERROR;
    }
    struct clib_container_hash_map_item **old_buckets = map->buckets;

    move_entries(old_buckets, new_buckets, map->capacity, new_capacity);

    map->buckets = new_buckets;
    map->capacity = new_capacity;
    map->threshold = map->load_factor * new_capacity;
    map->mem_free_func(old_buckets);
    return CLIB_RES_OK;
}


int clib_container_hash_map_put(struct clib_container_hash_map *map, void *key, void *value, void **pre_value) {
    if (!key) {
        return CLIB_RES_PARAM_ERROR;
    }
    if (map->size >= map->threshold) {
        //需要扩容
        int res = (resize(map, map->capacity << 1));
        if (res != CLIB_RES_OK) {
            return res;
        }
    }
    const size_t hash = map->hash_func(key, map->key_len, map->hash_seed);
    const size_t i = hash & (map->capacity - 1);

    struct clib_container_hash_map_item *replace = map->buckets[i];

    while (replace) {
        void *rk = replace->key;
        if (rk && map->key_cmp_func(rk, key, map->key_len) == 0) {
            if (pre_value != NULL) {
                //如果插入的是不同指针，再向上传递
                if (replace->value != value) {
                    *pre_value = replace->value;
                }
            }
            replace->value = value;
            return CLIB_RES_OK;
        }
        replace = replace->next;
    }

    struct clib_container_hash_map_item *new_entry = map->mem_malloc_func(sizeof(struct clib_container_hash_map_item));

    if (!new_entry) {
        return CLIB_RES_MEMORY_ERROR;
    }
    new_entry->key = map->mem_malloc_func(map->key_len);
    if (new_entry->key == NULL) {
        return CLIB_RES_MEMORY_ERROR;
    }
    map->mem_copy_func(new_entry->key, key, map->key_len);
    new_entry->value = value;
    new_entry->hash_value = hash;
    new_entry->next = map->buckets[i];

    map->buckets[i] = new_entry;
    map->size++;
    if (pre_value != NULL) {
        *pre_value = NULL;
    }
    return CLIB_RES_OK;
}

static size_t get_bucket_index(struct clib_container_hash_map *map, void *key) {
    size_t hash = map->hash_func(key, map->key_len, map->hash_seed);
    return hash & (map->capacity - 1);
}

int clib_container_hash_map_remove(struct clib_container_hash_map *map, void *key, void **out) {
    if (!key) {
        return CLIB_RES_PARAM_ERROR;
    }
    const size_t i = get_bucket_index(map, key);

    struct clib_container_hash_map_item *e = map->buckets[i];
    struct clib_container_hash_map_item *prev = NULL;
    struct clib_container_hash_map_item *next = NULL;
    while (e) {
        next = e->next;
        if (e->key && map->key_cmp_func(key, e->key, map->key_len) == 0) {
            void *value = e->value;
            if (!prev) {
                map->buckets[i] = next;
            } else {
                prev->next = next;
            }
            map->mem_free_func(e->key);
            map->mem_free_func(e);
            map->size--;
            if (out) {
                *out = value;
            }
            return CLIB_RES_OK;
        }
        prev = e;
        e = next;
    }
    return CLIB_RES_OUT_OF_BOUNDS_ERROR;
}

int clib_container_hash_map_get(struct clib_container_hash_map *map, void *key, void **out) {
    if (!key) {
        return CLIB_RES_PARAM_ERROR;
    }
    size_t index = get_bucket_index(map, key);
    struct clib_container_hash_map_item *bucket = map->buckets[index];

    while (bucket) {
        if (bucket->key && map->key_cmp_func(bucket->key, key, map->key_len) == 0) {
            *out = bucket->value;
            return CLIB_RES_OK;
        }
        bucket = bucket->next;
    }
    return CLIB_RES_BUSINESS_ERROR;
}

size_t clib_container_hash_map_get_current_size(struct clib_container_hash_map *map) {
    return map->size;
}


int clib_container_hash_map_get_keys(struct clib_container_hash_map *map, void **out_keys) {
    int result_index = 0;
    for (size_t i = 0; i < map->capacity; i++) {
        struct clib_container_hash_map_item *entry = map->buckets[i];
        while (entry) {
            out_keys[result_index] = entry->key;
            result_index += 1;
            entry = entry->next;
        }
    }
    return result_index;
}


int clib_container_hash_map_remove_all(struct clib_container_hash_map *map, void *out_values[]) {
    size_t i;
    int remove_index = 0;
    for (i = 0; i < map->capacity; i++) {
        struct clib_container_hash_map_item *entry = map->buckets[i];
        while (entry) {
            if (out_values != NULL) {
                out_values[remove_index] = entry->value;
            }
            remove_index += 1;
            struct clib_container_hash_map_item *next = entry->next;
            map->mem_free_func(entry);
            map->size--;
            entry = next;
        }
        map->buckets[i] = NULL;
    }
    return remove_index;
}


bool clib_container_hash_map_contains_key(struct clib_container_hash_map *map, void *key) {
    struct clib_container_hash_map_item *entry = map->buckets[get_bucket_index(map, key)];
    while (entry) {
        if (map->key_cmp_func(key, entry->key, map->key_len) == 0) {
            return true;
        }
        entry = entry->next;
    }
    return false;
}